package two.chapter_1.c1_1;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

public class Ex1_1_22 {

    public static void main(String[] args) {

        int a[]={3,9,2,6,1,7,4,8,5};
        Arrays.sort(a);
        StdOut.println("index:"+rank(8,a));

    }


    public static int rank(int key,int []a){

        return rank(0,key,0,a.length-1,a);
    }

    private static int rank(int level,int key, int lo, int hi, int[] a) {
        StringBuilder sb=new StringBuilder();
        for (int i=0;i<level;i++){
            sb.append(" ");
        }
        StdOut.println(sb.toString()+"rank(lo:"+lo+"hi:+"+hi+")");
        if (lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key-a[mid];
            if (cmp>0){
                lo=mid+1;
            }else if (cmp==0){
                return mid;
            }else {
                hi=mid-1;
            }
            level+=1;
            return rank(level,key,lo,hi,a);
        }

        return -1;
    }

}
